package class03

func lcst1(s1, s2 string) string {
	dp := make([][]int, len(s1))
	for i:=0; i<len(s1); i++ {
		dp[i] = make([]int, len(s2))
	}
	var maxLen, endIndex int

	row, col := 0, len(s2)-1
	for row < len(s1) {
		i, j := row, col
		lens := 0
		for i < len(s1) && j < len(s2) {
			if s1[i] != s2[j] {
				lens = 0
			} else {
				lens++
			}
			if lens > maxLen {
				maxLen = lens
				endIndex = i
			}
			i++
			j++
		}
		if col > 0 {
			col--
		} else {
			row++
		}
	}
	return s1[endIndex-maxLen+1:endIndex+1]
}

func lcst2(s1, s2 string) string {
	var rmaxLen, rendIndex int
	fn := func (maxLen, endIndex int){
		if maxLen > rmaxLen {
			rmaxLen = maxLen
			rendIndex = endIndex
		}
	}
	lcst2Process(s1, s2, len(s1)-1, len(s2)-1, fn)
	return s1[rendIndex-rmaxLen+1:rendIndex+1]
}

func lcst2Process(s1, s2 string, end1, end2 int, fn func(maxLen, endIndex int)) int {
	if end1 == 0 && end2 == 0 {
		if s1[end1] == s2[end2] {
			fn(1, end1)
			return 1
		}
		return 0
	}
	if end1 == 0 {
		if s1[end1] == s2[end2] {
			return 1
		} else {
			return lcst2Process(s1, s2, end1, end2-1, fn)
		}
	}
	if end2 == 0 {
		if s1[end1] == s2[end2] {
			return 1
		} else {
			return lcst2Process(s1, s2, end1-1, end2, fn)
		}
	}
	var p1, p2, p3 int
	p1 = lcst2Process(s1, s2, end1-1, end2, fn)
	p2 = lcst2Process(s1, s2, end1, end2-1, fn)
	p3 = lcst2Process(s1, s2, end1-1, end2-1, fn)
	if end1-1 >= 0 && end2 -1 >= 0 && s1[end1] == s2[end2] && s1[end1-1] == s2[end2-1] {
		p3 = p3 + 1
	} else if s1[end1] == s2[end2] {
		p3 = 1
	}
	fn(max(p1, max(p2, p3)), end1)
	return max(p1, max(p2, p3))
}